// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

func interpolationSearch(array []int, n int, target int) int {
	if n == 0 {
		return -1
	}

	low := 0
	high := n - 1

	for array[high] != array[low] && target >= array[low] && target <= array[high] {
		// 估计中间
		mid := low + ((target - array[low]) * (high - low) / (array[high] - array[low]))

		// 找到目标值
		if target == array[mid] {
			return mid
		} else if target < array[mid] {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}

	// 如果找到目标
	if target == array[low] {
		return low
	} else {
		return -1
	}
}

func main() {
	array := []int{2, 5, 6, 8, 9, 10}
	target := 5
	n := len(array)

	index := interpolationSearch(array, n, target)
	if index != -1 {
		fmt.Printf("Element found at index %d \n", index)
	} else {
		fmt.Println("Element not found in the array")
	}
}

//$ go run interview7-6.go
//Element found at index 1
